Nyongk 위키:Transactional Information System
Transactional Information Systems : Chapter 12. Crash Recovery : Notion of Correct 12.1 Goal and Overview crash recovery의 목적(goal) : failure resilience, fault tolerance, reliability * crash의 정의 : 데이터 서버를 다운시키고 휘발성 메모리의 데이터를 날려버리는 온갖 오류(failure)를 말한다. 단, 디스크(stable secondary storage)의 데이터는 온전하다고 본다. * crash recovery의 목적 : 서버를 재시작하고 permanent data를 가장 최근의 consistent state의 permanent data로 되돌리는 것이다. 보다 정확히 말하자면, 트랜젝션의 atomicity와 durability를 보장하는 것이다. * 가장 최근에 consistent 상태는 crash 이전에 실행된 직렬화된 순서에 따라 모든 commit된 갱신 사항을 반영하고, uncommit된 것이나 이전에 취소된 transaction 들은 제거한 상태를 말한다. * 가장 최근의 consitent state's permanent data : commit된 트랜젝션의 모든 변경사항은 적용되었고, uncommit 되거나 앞서 abort된 트랜젝션의 변경사항은 무시된것 in the serialization order of the original pre-crash execution. * failure가 발생했을 때 consistent 상태를 유지하거나 재구성하는 것을 보통 복원성(failure resilience), 내구성(fault tolerance), 또는 가장 일반적인 용어로 데이터 서버의 신뢰성(reliability)라고 말한다. * 데이터 서버의 reliability(신뢰성) (= failure resilience(복원성), = fault tolerance(내구성))의 정의 : failure를 맞닥드려도 consistent state를 유지하거나 재구성할 수 있는 능력. Redo와 Undo recovery * crash recovey의 성능은 트랜젝션 durability의 효율적인 구현에 달려있다. * crash 상황에서는 디스크(stable secondary sotrage)에 반영되지 못한 변경사항을 잃게 되므로, commit된 트랜젝션에 의해 만들어진 affected data updates의 redo recovory를 고려해야한다. * 또한 commit 되지 않은 transaction은 ACID 패러다임의 atomicity 특성에 따라 갱신 사항에 대해 undo recovery를 수행해야 하며 이 알고리즘은 transaction recovery와 개념적으로 동일하다. * 12장과 13장에서 설명하는 중요 아이디어는 crash recovery를 상대적으로 단순하고 관리 가능하게 유지하기 위해 redo, undo 각각에 대한 문제를 가능한 한 분리함으로써 이러한 상호작용을 최소화 하는 것이다. * uncommit된 트랜젝션의 경우, atomicity property는 변경사항의 undo recovery를 좌우한다.(dictate) * undo recovery 알고리즘은 transaction recovery에 표현된 ??과 동일하다. * crash recovery 알고리즘은 redo와 undo 단계 사이에 발생할수있는 민감한 상호작용을 고려해야한다. * 효율적인 crash recovery를 위해서는 redo와 unredo 고려사항을 최대한 많이 나누어서 이같은 상호작용을 최소화하는 것이다. * ACID 패러다임 (책에 없는 내용) ** 원자성(atomicity)은 트랜잭션과 관련된 일들이 모두 수행되었는지 아니면 모두 실행이 안되었는지를 보장하는 능력이다. ** 일관성(consistency)은 트랜잭션이 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 유지하는 것을 의미한다. ** 독립성(isolation)은 트랜잭션을 수행 시 다른 트랜잭션의 연산 작업이 끼어들지 못하도록 보장하는 것을 의미한다. ** 영속성(durability)은 성공적으로 수행된 트랜잭션은 영원히 반영돼야 함을 의미한다 Failure model : soft, fail-stop crash * soft crash : 디스크(secondary storage)의 데이터는 온전하게 유지되는 failure model ** hard crash : secondary sotrage media가 망가진 경우의 failure model. (이것은 16장에 다룸) * soft crash 모델은 실제 응용프로그램, 특히 운영체제나 데이터베이스 시스템 코드의 에러, 그리고 시스템 관리자에 의해 발생하는 에러 등의 데이터 서버 정지를 유발시키는 대부분의 failure를 포함한다. * soft crash가 일반적이며 실제 어플리케이션에 포함된 데이터 서버의 outstage를 일으키는 대부분의 failure와 특히 OS와 DB 시스템 코드에 포함된 소프트웨어 에러, 시스템 관리자에 의한 에러까지 포함한다. * soft crash의 가장 큰 원인은 소프트웨어 에러이다. 특히 하이? 버그가 문제이다. ** 예전에는 정전이 일반적인 원인이었으나 중요성이 적어지고있다. *하이? 버그(Heisenbug) : nondeterministic(비결정론적) 이고 동시에 실행되는 쓰레드에서 자주 발생하며, 과부하시 또는 일반적이지 않은 상황에서 발생하는 에러. 추적하고 재현하기 어렵다. *대규모 어플리케이션에서 하이? 버그를 다루는 최선의 방법은 **가능한 빨리 서버를 다운시키고, (= fail-stop) **ACID 패러다임에 따라 redo, undo 에 기반하여 consitent state로 서버의 permanent data를 복구시키고, **서버를 재시작 하는것이다. *위와같은 과정에서 서버는 초기화되기 때문에 하이? 버그가 다시 발생할 가능성을 아주 많이 낮춰준다. *fault-tolerant(무정지형 : 장애 발생시 다른 부품이나 절차가 역할을 대체 수행하여 서비스를 중단 없이 제공) 하드웨어와 OS에 기반한 지속적인 서버의 forward processing을 겨냥한 접근은 효율성이 떨어진다. **가장 성공적인 "직렬 컴퓨터 시스템"에서도 하드웨어 리소스의 nonstop 프로세싱을 결국 제한하게 됬으며 상위 소프트웨어 레이어에 전통적 crash recovery 알고리즘을 추가했다. *하이? 버그를 다룰 때 가장 중요한 점은 에러를 감지하면 즉시 다운되어야 한다는 fail-stop property를 가져야 한다는 것이다. *에러 탐지는 완벽할 수 없지만, 실제 시스템에서는 철저한 self-checking 방법을 사용해 신뢰할만한 탐지를 한다. Recovery performance and system availability * crash recovery 중에는 클라이언트가 서버에 접근할 수 없으므로 recovery 또는 restart 시간을 최소화 하는 것이 성능에 중요하다. * 시스템 가용성 (system availiablity) : MTTF / (MTTF + MTTR) ** MTTF : 서버가 다운되는 평균 시간 간격. (Mean Time To Failure) ** MTTR : 서버가 복구되는 평균 시간 (Mean Time To Repair) * 위의 수식은 빠른 recovoery가 가용성을 높인다는 것을 보여준다. * 성능을 위한 두번째 고려요소는 crash recovery를 위해 평상시 소비되는 추가적인 자원소비이다. ** ex) 로그파일에 로깅데이터 업데이트시 디스크 I/O가 추가로 요구된다. Correctness of recovery algorithm * crash recovery는 모든 가능한 상황에서 정확하게 작동해야 한다. * recovery algorithm이 전체적인 state space를 모두 다룰 필요는 없지만, recovery 도중에 crash가 중첩하여 발생하는 상황은 대비해야 한다. * 아무리 강조해도 지나치지 않다. * recovory 알고리즘은 거대한 state space를 처리할 필요가 있다. * state space는 알고리즘에 의해 철저히 보장(보호)받는 것이 확신하는 것은 사소한것이나 다름없다. * recovery 동안 crash가 또다시 발생할수 있다. 실제 어플리케이션에서는 드문 일이 아니다. Simplicity and Testability * large state space에서 crash recovery는 cache manager와 같은 module보다 testing이나 debugging이 어려우며 recovery module에 문제가 발생할 경우 data에 복구 불가능한 damage를 남기기 때문에 recovery code는 data server의 어떤 components보다 더 critical하다. 이런 이유에서 correctness reasoning(정확성 증명)은 가장 중요한 요소이다. * crash recovery가 다루는 large state space는 recovery 알고리즘의 테스트와 디버깅을 매우 어렵게 만든다. 캐쉬 매니저의 테스트보다 더 어렵다. * 또한 recovory 코드는 데이터 서버의 다른 구성요소들 보다 훨씬더 critical 하다. * 예를 들어 query processor는 오직 일시적인 손상을 일으키고 특정한 쿼리에 제한되는 경향을 보이지만, 반면에 잘못된 recovery 알고리즘은 임무수행에 필수적인 데이타(mission-critical data)에 영구적이고 돌이킬수 없는 손상을 일으키게 된다. * 위와 같은 이유로 correctness reasoning이 강조된다. * 올바른 crash recovery를 향한 중요한 걸음은 가능한 단순하게 알고리즘을 유지하는 것이다. * 그 다음으로 correctness의 증명을 쉽게 하고 software적인 testing을 지원하기 위해 simplicity를 중요시 여긴다. Simplicity의 최근 관점은 systems의 평상시(normal operation)에 동작하는 code를 reuse해서 recovery algorithm를 위한 reusing code를 사용하는 것이다. *simplicity는 correctness reasoning 사용을 완화시키고, 또한 소프트웨어 테스트를 지원한다. * 시스템의 normal operation를 위해 작성되고 테스트된 코드를 recovery 알고리즘에 재사용한다. * 이같은 실용적인 고려사항의 예를 나중에 들것이다. Correctness reasoning(정확성 증명) * correctness reasoning에 대한 내용은 없다. !!! * (정확성을 증명하기 위한) 간결성(Simplicity)는 대단히 매력적이지만 Simplicity와 성능(performance)는 trade-off 관계에 있기 때문에 recovery algorithm의 성능을 낮춘다는 단점이 있다. * 13장에서 알고리즘의 복잡도 순으로 다양한 recovery algorithm을 살펴볼 것이다. 12.2 System Architecture and Interface * crash recovery와 관련된 system architecture의 component들은 다음과 같이 구성해야 한다. ** stable database *** stable device에 존재하며 page의 정보를 저장한다. 흔히 자기 디스크(HDD)등을 사용하는 보조 저장장치로 구성된다. *** stable storage에 저장된 page로 구성되어 있다. *** stable storage : soft crash에서 회복하는 모든 storage media. 일반적으로 자기디스크 또는 비휘발성 RAM. ** database cache *** 휘발성 메모리로 복사된 stable database page의 부분집합. *** 모든 데이타베이스는 캐쉬상에서 수행되고 후에 "flush" 액션으로 stable database로 다시 복사된다. *** 동일한 page라면 cache된 page가 stable database에 존재하는 page보다 최신이다. *** in that its contents captures more updates. *** database cache와 stable database에서 cache되지않은 apge는 함꼐 cached database를 구성한다. ** stable log *** cached database의 update 내역(update history)를 설명한 log entry로 구성된다. **** log entry는 recovery가 undo 또는 redo 하기에 충분한 정보를 포함한다. **** the update depending on the outcome of the corresponding transaction. **** 그러나 더 특성화된 log entry의 포맷을 상상할수있다. *** stable storage에 저장된 stable log는 일반적으로 단수 또는 복수개의 파일에 기록된다. ** log buffer *** stable log에 log entry를 기록하기 위한 버퍼로서, 휘발성 메모리 내에 위치한다. *** log entry는 먼저 log buffer에 기록되고 "force" 액션으로 stable log에 복사된다. * crash recovery 관한 한, 오로지 위의 4가지요소가 system state를 결정한다. * database cache와 log buffer는 crash 발생시 손실되는 휘발성 메모리에 위치하므로 recovery 알고리즘의 입력값은 stable database와 stable log에 의존한다. * 대부분의 stable log는 대부분 sequential append-only file(순차적으로 추가)로 구현되나 본 장에서 다루는 architectural model은 random access file내에서 database page들의 버전 별로 alternative하게 구현되는 형태를 취할 것이고, 이러한 형태를 shadow database라고 부른다. * stable log는 대부분 순차적인 append-only 파일로 구현된다. 그러나 이 책에서 다루는 아키텍쳐 모델은 random access file에 database page를 조직하는 shardow database 같은 alternative 구현도 허용한다. Transaction recovery reconsiderd * 함께 고려되는 stable log와 log buffer는 또한 normal operation 동안 abort된 트랜젝션을 roll back 하기위한 undo 정보를 제공한다. 따라서 log entry는 트랜젝션 recovoery와 crash recovery에 도움이 된다. * 트랜젝션 recovery 알고리즘은 빠른 접근을 위해 메모리에 log entry 카피본을 유지할 수 도 있다. 이것은 특히 stable log에 포함된 entry인 경우가 많다. * ?? 트랜젝션 중단은 random disk access를 요구하고 다른점에서는 stable log의 순차적인 write 패턴과 조화한다. Action during normal operation * 시스템은 normal operation동안 system state를 바꾸는 다양한 액션을 수행한다. 그리고 변경된 system state는 어느정도는 recovery 알고리즘에 영향을 끼친다. * 아래 리스트에는 위에서 언급한 system 액션을 카테고리별로 정리했다. * 시스템에 의해 실행되는 각각의 액션은 unique한 sequence number가 할당되고, 액션은 다양한 system component와 다른 액션의 의해 참조될 수 있다. Sequence number * 같은 페이지를 참조하는 액션들, 같은 트랜젝션을 참조하는 액션들이라고 해도 액션의 sequence number는 모두 다르다. sequence number는 지속적으로 증가된 값은 할당한다. # Transaction actions ## begin(t) ##* 트랜젝션 t의 시작을 나타낸다. ## commit(t) ##* 트랜젝션 t의 성공적인 완료를 나타낸다. 그 결과, 트랜젝션의 모든 update가 commit되어 soft crash가 발생해도 지속됨을 보장받는다. ## rollback(t) ##* 트랜젝션 t의 실패를 나타낸다. 트랜젝션의 모든 update들은 취소되어 cached database에 update가 남아있지 않게 된다. ## save(t) ##* 트랜젝션은 savepoint까지 rollback을 요청할 수있다. savepoint 이전까지 만들어진 모든 update는 보존된다. ## restore(t, s) ##* 트랜젝션 t를 savepoint s까지 rollback 한다. s 는 sequence number 이다. ##* save와 resotre는 여기서 다루지 않는다. 15장 3절에서 다시 생각해 볼 것이다. # Data actions ## read(p, t) ##* 트랜젝션 t를 대신해 page p를 읽는다. ##* (추가내용) transaction t의 해당 pageno인 page를 읽는다. 여기서 굳이 page 단위로 나눈 이유는 공간관리를 좀더 simple하게 하기 위해서이다. ##* (추가내용 포함) 해당 page를 database cache내의 고정된 가상메모리주소(fixed virtual-memory address)에다 고정시켜(pinning) 놓기 때문에 cache로부터 drop시키거나, 메모리 내부에서 이동되면 안 된다. Page contents를 읽고 난 후 page는 풀어지게(unpinning) 된다. 그 이유는 메모리 관리자에 의한 replacement를 방지하기 위해서이다. ##* page p는 database cache의 고정된 가상메모리 주소(fixed virtual-memory address)에 고정된다(pin). 왜냐하면 cache에서 drop되거나 memory로 이동하면 안되기 때문이다. ##* page p의 content를 이용한후 마침내 page를 고정해제(unpin)하게 된다. ## write(p, t) ##* 트랜젝션 t를 대신해 page p를 읽거나 쓴다. ##* read 와 동일하게 database cache에 page를 pin, unpin 한다. 차이점은 unpin 될때 page가 수정됬거나 "dirty" 되었다고 명시되는 점이다. ##* write 액션의 이런 개념은 previous read를 포함하므로, 또한 page 내부의 byte-level operation과 같은 page modifications도 포함한다. ##* 이런 방식의 write 액션을 physiological action 이라 부른다. ##* (추가내용) 실제 write시에는 page에 latch를 잡는데 이것은 해당 page가 flush되는 것을 방지하기 위함이다. ## full-write(p, t) ##* 트랜젝션 t를 대신해 page p를 쓴다. ##* write와는 대조적으로 일반적인 write 액션인 full-write는 page 를 수정하기 전에 page를 읽지 않는다. 오히려 full-write는 page의 모든 byte에 값을 기록한다. ##* 이런 방식의 액션을 "physical action"이라 한다. ## exec(op, obj, t) ##* 트랜젝션 t를 대신해 database object obj 상에서 database operation op를 실행한다. ##* database operation의 실행은 database page에 대한 read, write 액션 등등의 다른 액션을 유발할 수 있고, 또다른 database operation을 호출할수도 있다. ##* database operation은 시스템 인터페이스의 "native" operation 또는 읽어드린 abstract data type의 instance 상의 사용자정의 operation도 해당된다. ##* #"native" operation : data recored를 저장하거나 search key로 data record를 찾는 등의 operation. # Caching actions ## fetch(p) ##* stable database에서 datbase cache로 cache되지 않은 page p를 복사한다. ## flush(p) ##* stable database로 cache된 page p를 복사한다. 그리고 cache에는 page p가 아직 남아있다. ##* flush action은 오직 dirty page에서만 호출된다. stable page보다 cache된 page가 최신일 경우 dirty page라 한다. ##* flush 액션의 목적 : stable page를 최신의 것으로 유지하고, cache된 page의 상태를 "dirty"에서 "clean"으로 되돌리는 것이다. # log actions ## force() ##* 강제로 log buffer의 모든 log entry를 stable log로 복사한다. * 4개의 major system components와 그 사이에서 실행되는 액션은 다음 그림과 같다. thumb|left|400px * system이 시작될때 recovery 알고리즘이 첫단계로 호출된다. * 그래서 system은 항상 crash 후 곧바로 recovery 알고리즘이 시작될것이라 가정한다. * 전체 recovery 과정을 restart(.) action 이라고 부를 것이다. * 만약 restart 가 stable storage상의 단서에서 system history의 마지막 event가 normal shutdown이라는것을 찾아내면 recovery의 모든 과정을 skip 될수도 있다. * 다음장에서 보게될것은 recovery work 의 필요성이 어떻게 받아들여지는지의 그 상세함은 recovery 알고리즘 자체에 달려있다. 12.3 System Model * 12.3장에서는 앞서 설명한 system architecture에 대해 좀더 자세히 알아보도록 한다. 이곳에서 배운 내용은 13장에서의 correctness reasoning을 위한 초석이 된다. * recovery의 목적은 복구된 database에는 실행된 transaction들의 순차적 순서(serialization order)에 따라 모든 commit된 update들이 반영이 되어야 한다는 것이다. * system history는 recovery의 correctness을 위한 중요한 참조 포인트(reference point)가 되며 이를 위해 system history에 추가사항들이 필요하다. 특히 recovery에 관한 caching action들이 history에 저장되야 한다. h5. Extended history * 정의 : Transactional data server의 Extended system history는 root가 transaction ID이나 caching action으로, leaves가 transaction action이나 data action으로 이루어진 tree들이 모인 forest와도 같다. * 이제 부터는 extended system history를 history라고 부르겠다. h5. Stable log * history 중 force에 의해 보조저장장치에 저장된 action들의 log entry의 모임을 stable log라고 한다. h5. Log entries * 정의 : history에서, stable log는 history의 action set의 순이고 이는 history의 순서와 일치한다. 이러한 log된 action을 log entry라고 부른다. * log entry가 생성될 때는 해당 log가 redo로 사용될지, undo로 사용될지 결정되지 않으므로 logging된 action 그 자체를 다루는데 중점을 둔다. * 한 action의 input parameter가 다른 action의 result parameter에 의존할 수 있으므로 이런 result parameter는 log entry에 명확히 저장되어야 한다. h5. Log buffer * 정의 : history 중 아직 stable log에 기록되지 않은 최신의 action들의 log entry의 모임을 log buffer라고 한다, h5. Database state * stable database나 cached database를 위해 모든 date 조직 자체를 형식화 할 필요는 없다. * database내의 update의 존재 유무를 찾아 어떻게 logging된 action과 관계를 맺는지, 그리고 어떻게 recovery가 database state에서 진행되는지에 대해 집중하는게 낫다. h5. Page sequence number as state identifiers * 결과상태(resulting state)는 database에서 수행된 action들의 순서에 의해 영향을 받기 때문에 형식적인 정의(formal definition)에 의한 action들의 순서에 대한 정보를 얻어야 한다. * update되는 정확한 순서를 얻기 위해서 database page가 제공하는 page sequence number를 사용해 순서에 대한 부분적인 정보를 얻는다. * 각각의 database page에는 sequence number가 붙어있고, 이 sequence number는 그 page에서 실행된 특정 type의 가장 최신의 action을 추적 할 수 있게 해준다. * page sequence number는 page 내에 포함되어 있기 때문에 fetch되거나 flush 될 때도 page와 함께 복사된다. * page sequence number를 사용하지 않고 모든 data에 sequence number나 transaction ID를 다는 것은 page sequence number를 사용하는 것에 비해 높은 overhead를 야기한다. * page sequence number를 사용해 write action들에 대한 정보를 얻을 수 있다. 예를 들면 Sequence number s인 page가 있을 때 s보다 작은 sequence number를 가지는 모든 write action은 이미 s인 page에 적용되었다는 것을 뜻한다. * page sequence number를 사용해도 앞선 action들 사이의 순서는 알지 못하지만, 이러한 정보는 recovery algorithm에 있어서 필수적이지 않다는 사실을 보게 될 것이다. * cached database의 page sequence number는 history의 가장 최근의 write action의 sequence number와 일치한다. * stable database에서의 page sequence number은 page에 행해진 가장 최근의 flush action 바로 전 (가장 최근의) write action의 sequence number와 일치한다. h5. Cached database * history에서, cached database는 history의 모든 full-write를 포함한 write action의 순서화된 부분집합이다. * 그러므로, history에 있는 action들은 모두 cached database에 포함되어 있다. h5. Stable database * 제공된 system history에서, stable database는 history의 순서에 따라 수행된(ordered) 모든 write action(full-write action 포함)들의 부분적인 순차 모음이고, 각 page는 page number p를 가지고 있다. * history에서 flush action에 앞서 수행된 모든 write action은 stable database에 포함된다. * history에 있는 flush 이전 action들은 모두 stable database에 포함되어 있다 h3. 12.4 Correctness Criterion(일치성 기준) * 형식화 모델(formal model)의 building block을 정의하기 위해 crash recovery를 만족하기 위한 일치성 기준(correctness criterion)이 필요하다. * 일치성 기준을 위해 database history가 순서대로 보존되어 있으며, 복구할 log들이 순차적으로 잘 보존되어 있음을 가정한다. * simply 보다 crash recovery를 correct한다는 것은 system failure들로부터 commit된 transaction들의 뿌리들(root)들을 보존한다는 의미이다. h5. Correct crash recovery * 정의 : 시스템 failure 이 후 수행되는 recovery algorithm이 수행중에 반복되는 crash에도 불구하고 commit된 action의 순서대로 cached database에 수정된 내용이 반영함을 보장할 때 이 crash recovery algorithm은 올바르다(correct)고 한다. * 위 정의에서 stable database가 아닌 cached database를 언급한 이유는 가용성(availability)을 최대한 높이기 위해 recovery가 완료 된 후 flush 연산을 시행하지 않기 위해서이다. * stable database의 경우 flush 하는 것 만으로 correct crash recovery 상태를 만들 수 있지만, 이 부분은 버퍼 관리자의 영역이므로 더 이상 언급하지 않는다. * log에 적절한 정보가 없다면 recovery 알고리즘은 recovery를 수행할 수 없다. h5. Logging rule * 정의 : recovery algorithm은 다음 사항을 만족시킨다. ** redo logging rule *** ACID paradigm의 durability를 보장하기 위해 commit이 수행된 history내의 모든 transaction들은 stable log에 저장되어야 한다. *** redo가 필요한 정보가 저장됨을 보장한다. ** undo logging rule *** ACID paradigm의 atomicity를 보장하기 위해 commit이나 rollback이 수행되지 않은 history내의 모든 transaction 의 data action은 stable database에 존재하는 경우 stable log에도 저장된다. *** page가 stable database에 flush 되기전에 undo 정보를 stable log에 저장하는 것을 강제한다. 이를 WAL protocol이라고도 한다, *** undo에 필요한 정보가 저장됨을 보장한다. ** Garbage collection rule *** History내의 모든 transaction의 data action에 대해 stable log내에 존재하지 않는다는 것은 해당 page가 commit에 의해 stable database에 저장되었다는 뜻이다. *** 더 이상 필요 없는 log를 삭제하기 위한 기준이다. *** 필요 없는 log를 삭제함으로써 recovery 시 recovery 시작점을 앞으로 당겨 recovery의 범위를 줄임으로써, recovery를 최적화 한다. h3. 12.5 Road Map of Algorithm * 12.4에서 살펴본 logging rule은 모든 correct recovery algorithm에서 필수적이지만, 몇몇 알고리즘은 stable log와 stable database, cached database사이에서 좀더 엄격한 관계를 요구한다. * algorithm을 구분하는 기준은 restart 과정에서 undo와 redo를 각각 실행하는가 여부이다. 이에 따라 다음의 4가지 case로 나누게 된다. {center} | | steal | no-steal | | force | undo \\ no-redo | no-undo \\ no-redo | | no-force | undo \\ redo | no-undo \\ redo | {center} * force :* *commit 된 transaction의 update들을 가진 모든 page들은 확실하게 commit point에 맞추어 flush되는지 여부(성능 이슈) ** force를 사용하면 recovery시 redo가 필요 없어지나 동일 page가 여러번 commit되어도 매번 stable database에 저장해야 하기 때문에 성능이 떨어진다. ** force를 사용하지 않을 경우 recovery시 redo가 필요하나 force에 비해 성능이 좋다. ** force 사용 시 page write 이전 commit log를 먼저 쓰기 때문에 write 중 crash가 발생했을 경우에도 undo를 하지 않는다. * steal : commit되기전에 transaction이 갱신한 page를 stable database에 반영될 수 없는지의 여부(공간 이슈) ** steal을 사용하지 않을 경우 recovery시 undo가 필요 없어지나 commit되지 않은 page는 cold하다고 해도 메모리 버퍼에 그대로 남아 있어야 하므로 버퍼 사용에 불이익을 얻는다. 특히 메모리 버퍼의 크기가 작다면 데드락에 걸리는 현상이 발생 할 수도 있기 때문에 많은 양의 메모리 버퍼를 사용해야 한다. ** steal을 사용하면 recovery시 undo가 필요하나 no-steal로 인한 문제가 없다. h5. No-undo / No-redo algorithms (no-steal / force) * no-undo / no-redo algorithms ** stable database가 commit된 transaction의 action이 수행된 page만을 정확히 유지한다. 즉, commit된 page는 바로 stable database로 flush하고, 그렇지 않은 page는 stable database로 이동하지 않는다. ** crash가 발생해도 restart 중 undo 및 redo가 전혀 필요하지 않다. ** 특정 page 내 commit 되지 않은 record가 존재하는 상태에서 동일 page 내 record가 commit될 경우 정책이 깨지기 때문에 page단위 미만의 locking(ex. record level locking)은 사용할 수 없다. h5. No-undo / With-redo algorithms (no-steal / no-force) * no-undo / with-redo algorithms ** commit이 되지 않은 transaction의 어떤 action이 수행된 page도 stable database로 저장하지 않는다. ** stable database내 특정 transaction의 action이 존재한다면 이 transaction은 반드시 commit되었다는 것을 보장한다. ** commit된 모든 page가 stable database로 복사되는 것은 아니므로 crash가 발생한다면 restart 중 redo만이 요구되고 undo는 요구되지 않는다. ** 특정 page 내 commit 되지 않은 record가 존재하는 상태에서 동일 page 내 record가 commit 될 경우에 해당 page가 디스크에 내려가지 않으므로 정책이 깨지지 않아 page단위 이하의 locking도 사용할 수 있다. 다만 이 경우 crash가 발생 했을 때 redo해야 하는 범위가 증가하므로 recovery 성능에 악영향을 끼친다. 또한 record level locking 사용시 page locking을 사용할 때 보다 더 많은 버퍼 공간을 필요로 한다. h5. With-undo / No-redo algorithms (steal / force) * with-undo / no-redo algorithms ** stable database에 commit된 transaction의 *action이 수행된 page{*}을 반영한다. ** 특정 transaction이 commit된다면 해당 transaction의 모든 data action은 stable database에 반영되었음을 보장한다. ** commit되지 않은 page가 stable database에 복사 될 수 있으므로 crash가 발생한다면 restart 중 undo만이 요구되고 redo는 요구되지 않는다. ** 특정 page 내 commit 되지 않은 record가 존재하는 상태에서 동일 page 내 record가 commit 될 경우에 해당 page가 디스크에 저장되므로 정책이 깨지지 않아 page단위 이하의 locking도 사용할 수 있다. 다만 이 경우 crash가 발생 했을 때 undo 해야 하는 범위가 증가하므로 recovery 성능에 악영향을 끼칠 수 있다.(no-undo / with-redo로 인한 성능 저하보다는 덜 치명적이다.) h5. With-undo / With-redo algorithms (steal / no-force) * with-undo / with-redo algorithms ** 일반적으로 steal / no-force라고 불린다. ** crash 이후 restart시 undo와 redo를 모두 수행한다. ** 특정 page 내 commit 되지 않은 record가 존재하는 상태에서 동일 page 내 record가 commit 될 경우에 정책이 깨지지 않아 page단위 이하의 locking도 사용할 수 있다 h5. Deferred update algorithms * 두 개의 no-undo 카테고리들(no-steal / no-force와 no-steal / force)을 deferred update algorithm이라고 부른다. * deferred update algorithm은 성공적으로 commit될때 까지는 stable database에 update하는 것을 연기하며 이런 알고리즘은 stable log의 다양한 기반을 바탕으로 구현이 가능하다. ** no-steal database cache : stable log는 log entry의 sequential append only형식의 파일로 이루어 지며, log entry는 redo 정보만 가지고 있으면 된다 ** shadowing approach : stable log에 아직 commit 되지 않은 transaction의 update로 이루어진 page를 구성한다. 일단 2개의 page addressing table을 생성한 후 page number를 disk내 address로 변환하는 값을 저장해 두고 commit 되지 않은 상태에서 update 수행시 새 page를 생성하고 addressing table 중 하나에 등록한다. 이때, 나머지 table는 계속 기존의 page를 가리킨다. commit될 경우, 예전 page의 정보를 가진 address table에서 새로 생성된 page의 정보를 가진 address table로 master pointer를 옮기고 기존 page를 free space management로 release한다. 이 때 address table에서 master pointer를 옮기는 작업을 install이라고 한다. undo가 필요할 경우에는 table만 복구하면 된다. 또한 old page version들은 잠깐 동안 new page version들과 공존하게 되는데, 이럴 때의 old page들을 “shadow page”라고 부른다. 또한 이러한 것들을 모은 변하지 않은 database를 “shadow database”라고 부른다. 덧붙여서. Shadowing기법이 commit전에 강제로 new page version들을 disk로 반영시키지 않는 한, stable log는 여전히 redo information을 필요로 하며 보통 이것들은 별개의 파일로 만들어 진다. ** versioning approach : stable log file은 database object들의 버전들을 가진다. cached database 및 stable database는 모두 commit이 되기 전까지는 변경되지 않는다. transaction의 update 시 새 version을 만들고 commit이 된다면 transaction으로 만들어진 모든 version을 cached database에 이동한다. shadowing approach과 유사하게 object별로 pointer를 switching하는 연산이 수행되어 새로운 version을 “install” 시키거나 필요한 경우 물리적으로 copy 한다. 이러한 개별 file들은 intention list 라고 불린다. Shadowing 기법과 같이 new version들이 commit전에 disk로 force되어지지 않는다면, stable log내의 redo 정보가 반드시 필요하다. h5. Update-in-place algorithms * 두 개의 with-undo 카테고리들(steal / no-force와 steal / force)을 update-in-place algorithm이라고 부른다. 이는 update 수행시 원본 database page에 바로 update를 하는 방식이다. * 아래 그림은 앞서 말한 algorithm을 설명하는 그림이다. thumb|left h5. The case for no-undo / no-redo algorithms * no-undo / no-redo algorithm의 경우 항상 올바른 상태(correct state)를 유지한다는 점에서 사실상 즉각적인 recovery를 수행한다고 볼 수 있다. * 평상시(normal operation) recovery가 발생시키는 추가 작업이 많으므로 상당한 오버헤드 비용을 발생시킨다. h5. Cost of no-undo * no-undo 혹은 deffered-update의 구현은 page-oriented shadowing 접근 방식 이나 versioning 접근 방식을 사용한다. * page-oriented shadowing 방식의 경우 commit 시간에 전체 페이지를 install 하는 것이 제한되어 있으므로 page 레벨 미만의 concurrency control은 사용할 수 없다. * versioning 접근 방법을 사용할 경우 transaction의 commit이 많은 양의 추가 작업을 초래한다. 최악의 경우 모든 새 버전의 복사, transaction의 update action의 재실행이 필요하다. h5. Cost of no-redo * no-redo를 위한 방법은 transaction commit시 수정된 모든 page를 flush하는 것이다. 이 방법은 전형적으로 transaction commit에의해 수정되었던 페이지 수만큼 stable database에 많은 임의의(random) 디스크 I/O를 발생시킨다. * commit된 transaction의 log entry를 저장하기 위한 순차적(sequential) 디스크 I/O에 비해 10배 이상의 추가 비용이 발생할 것이다. 정리하면, no-redo 알고리즘의 force 정책은 성능적인 측면에서 수용할 수 없다. {tip:icon=false}* with-undo / with-redo 알고리즘은 평상시 cached database, stable database, stable log 사이의 관계에서 어떤 가정도 하지 않는 가장 일반적인 것이고, crash 후 필요하다면, undo와 redo를 할 수 있게 한다. * 13장에서 보겠지만, restart 시 undo와 redo의 양을 제한 하는 효과적인 방법이 존재하며 이 방법을 통해 recovery time을 수용 가능한 수준으로 끌어올린다. * with-undo / with-redo 알고리즘은 빠른 restart를 위한 평상시 증가된 오버헤드의 trade off와 관련된 유연성(flexibility)을 제공한다. 이는 crash recovery 알고리즘을 변경하지 않고도 cache manager가 dirty page를 flush하는 것을 증대하는 것으로 달성할 수 있다. * 정리하면, with-undo / with-redo 알고리즘은 상업적인 시스템에서 사용할 수 있는 유일한 방법이다.{tip}